package teach.sort;

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        //创建数组
        int[] array = {8, 1, 4, 9, 0, 3, 5, 2, 7, 6};

        //输出数组，观察原数组
        System.out.println(Arrays.toString(array));
        System.out.println();

        //比较一次，换位一次
        //sortByNtemp(array);

        //直接保存，比较完，换位一次
        sortBy1Temp(array);

    }

    public static void sortByNtemp(int[] array){
        //假定下标0为最大或最小，从下标1开始反复和左边对比
        for(int i=1;i<array.length;i++){
            //当前需要找到自己位置的元素的下标
            int j = i;
            //下标为1时，进行最后一次比对
            while(j>0){
                //if(array[j]>array[j-1]){//降序，排序的走向选择
                if(array[j]<array[j-1]){//升序
                    //当左侧比右侧大时，进行换位
                    int temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                    //j自减，表示找位置的元素在向左移
                    j--;
                    //输出，观察排序的变动
                    System.out.println(Arrays.toString(array));
                }else{
                    //不满足条件，则表示，右侧比左侧大，因为左侧顺序是排好的，所以不需要再比较下去了。
                    //停止这一次的比对循环
                    break;
                }
            }
            System.out.println();
        }
    }

    public static void sortBy1Temp(int[] array){
        //假定下标0为最大或最小，从下标1开始反复和左边对比
        for(int i=1;i<array.length;i++){
            //当前需要找到自己位置的元素的下标
            int j = i;
            int temp = array[j];//直接将进行比对的元素临时保存
            //下标为1时，进行最后一次比对
            while(j>0){
                //if(array[j]>array[j-1]){//降序，排序的走向选择
                if(temp<array[j-1]){//升序
                    //当左侧比右侧大时，直接将左侧的右移，覆盖右侧
                    array[j] = array[j-1];
                    //j自减，表示找位置的元素在向左移
                    j--;
                    //输出，观察排序的变动
                    System.out.println(Arrays.toString(array));
                }else{
                    //不满足条件，则表示，右侧比左侧大，因为左侧顺序是排好的，所以不需要再比较下去了。
                    //停止这一次的比对循环
                    break;
                }
            }
            //将临时保存的元素赋值给当前位置
            array[j] = temp;
            System.out.println(Arrays.toString(array));
            System.out.println();
        }
    }
}
